{\magonebf 3.8 Sets  (set)}

\decl set E 

{\bf 1. Definition}

An instance $S$ of the parameterized data type \name\ is a collection of 
elements of the linearly ordered type $E$, called the element type of $S$. The 
size of $S$ is the number of elements in $S$, a set of size zero is called the 
empty set.


\bigskip
{\bf 2. Creation}


\create S {} 

creates an instance \var\ of type \name\ and initializes it to the empty set.

\bigskip
{\bf 3. Operations}

\+\cleartabs & \hskip 1.8truecm & \hskip 6truecm &\cr
\+\op void insert  {E\ x} 
                         {adds $x$ to \var}
\smallskip
\+\op void del     {E\ x} 
                         {deletes $x$ from \var}
\smallskip
\+\op bool member  {E\ x} 
                         {returns true if $x$ in \var, false otherwise}
\smallskip
\+\op E    choose  {}    
                         {returns an element of \var.}
\+\nop                   {\precond \var\ is not empty.}
\smallskip
\+\op bool empty   {}    
                         {returns true if \var\ is empty, false otherwise}
\smallskip
\+\op int  size    {}    
                         {returns the size of \var}
\smallskip
\+\op void clear   {}    
                         {makes \var\ the empty set}


\bigskip
{\bf 4. Iteration}


{\bf forall}($x,S$) 
$\{$  ``the elements of $S$ are successively assigned to $x$''  $\}$

\bigskip
{\bf 5. Implementation}

Sets are implemented by randomized search trees ([AS89]). Operations insert,
del, member take time $O(\log n)$, empty, size take time $O(1)$, and clear 
takes time $O(n)$, where $n$ is the current size of the set.

